1. Field of the Invention
The present invention relates generally to databases and, in particular, evaluation of database queries.
2. Description of the Background Art
Information is typically retrieved from a database through the use of queries. A database management system (DBMS) controls the creation, maintenance, and use of a database by responding to queries. When the DBMS receives a query, it evaluates the query to determine which information is being requested from the database, and responds to the query with the requested information.
One way to specify the information being requested in a query is through the use of a positional text condition. These are typically either phrase conditions where a set of search terms must collectively appear in a precise order within a column cell value of the database, or a proximity condition where a set of search terms must appear within a specific distance of each other within a column cell value of the database, in order to satisfy the condition.
In the case of phrase conditions, these are typically expressed by requesting result rows in which a particular column of a table in the database (e.g., SERVICE_ORDER.PROBLEM_DESCRIPTION) contains a phrase in the precise ordering specified (e.g., “unable to connect”). In the case of proximity conditions, these are typically expressed by requesting result rows in which a particular column of a table in the database (e.g., SERVICE_ORDER.PROBLEM_DESCRIPTION) contains one or more search terms within a certain number of words of each other (e.g., the word “connection” is found within four words of the word “dropped”).
There has been an interest among database vendors, Internet search vendors, and other specialty information retrieval product vendors in the ability to quickly identify a set of documents that each contain some specific phrase. Similarly, there is also interest in quickly identifying a set of documents containing a specific set of words where those words are found within a specified distance from each other. These functions are commonly accomplished by the aforementioned phrase conditions and proximity conditions, respectively.
Additionally, there has been recent interest in the use of bitmap-based method for evaluation of a set of conditions over columns from a single table. These bitmap-based methods enable the efficient combination of the effects of multiple conditions, which are each using some index-based evaluation method, until finally the precise set of rows relevant to a specified query has been identified and can then be projected.
Ideally, it would be useful to improve processing of queries that involve positional text conditions and conditions that can be represented using bitmap-based methods for evaluation. Accordingly, what is desired is efficient processing of sets of conditions that include a positional text condition.